package zw_401_500.zw_496_下一个更大元素I;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

class Solution {

    public static void main(String[] args) {
        int[] nums1 = {4, 1, 2}, nums2 = {1, 3, 4, 2};
        int[] element = nextGreaterElement(nums1, nums2);
        for (int i = 0; i < element.length; i++) {
            System.out.println(element[i]);
        }
    }

    /**
     * 方法二：单调栈 + 哈希表
     * 求大于某个数的第一个元素、下一个更大元素...这种类似的字眼的，都是单调栈的题目
     * 时间复杂度：O(m+n)，其中 m 是nums1的长度，n 是 nums2的长度。
     * 我们需要遍历nums2以计算nums2中每个元素右边的第一个更大的值；需要遍历nums1以生成查询结果。
     * 空间复杂度：O(n)，用于存储哈希表。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }


//    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
//        int len1 = nums1.length, len2 = nums2.length;
//        int[] ans = new int[len1];
//        for (int i = 0; i < len1; i++) {
//            ans[i] = -1;
//        }
//        for (int i = 0; i < len1; i++) {
//            for (int j = 0; j < len2; j++) {
//                if (nums1[i] == nums2[j]){
//                    while (j < len2 - 1) {
//                        j++;
//                        if (nums1[i] < nums2[j]) {
//                            ans[i] = nums2[j];
//                            break;
//                        }
//                    }
//                }
//            }
//        }
//        return ans;
//    }
}